﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PriorityQueue
{
    class PriorityQueue
    {
        class Heap<T>
            where T : IComparable
        {
            public Heap()
            {
                heap = new List<T>();
                heap.Add(default(T));
            }

            public void Add(T element)
            {
                heap.Add(element);

                int last = heap.Count - 1;

                while (last != 1)
                {
                    int other = last / 2;

                    if (heap[last].CompareTo(heap[other]) < 0)
                    {
                        T temp = heap[last];
                        heap[last] = heap[other];
                        heap[other] = temp;
                    }
                    else
                    {
                        break;
                    }

                    last = other;
                }
            }

            public T Pop()
            {
                int last = heap.Count - 1;

                if (last == 0)
                {
                    throw new Exception("No more elements");
                }

                T result = heap[1];
                heap[1] = heap[last];
                heap.RemoveAt(last);
                --last;

                int current = 1;

                while ((current * 2) <= last)
                {
                    int other;
                    if ((current * 2) == last ||
                        (heap[current * 2].CompareTo(heap[(current * 2) + 1])) < 0)
                    {
                        other = current * 2;
                    }
                    else
                    {
                        other = (current * 2) + 1;
                    }

                    if (heap[current].CompareTo(heap[other]) > 0)
                    {
                        T temp = heap[current];
                        heap[current] = heap[other];
                        heap[other] = temp;
                    }
                    else
                    {
                        break;
                    }

                    current = other;
                }

                return result;
            }

            private List<T> heap;
        }

        static void Main(string[] args)
        {
            int MAX = 50;
            Random rand = new Random();
            Heap<int> intHeap = new Heap<int>();

            for (int i = 0; i < MAX; i++)
            {
                int elem = rand.Next(100);
                Console.WriteLine(elem);
                intHeap.Add(elem);
            }

            Console.WriteLine("--------------------------");

            for (int i = 0; i < MAX; i++)
            {
                int elem = intHeap.Pop();
                Console.WriteLine(elem);
            }
        }
    }
}